package test_314;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张杰
 * Date: 2022-03-14
 * Time: 11:50
 */
public class TestDemo {

    /* 求的是出现次数最多的单词
     * @param words
     * @param k
     * @return List<String>
    */
    public List<String> topKFrequent(String[] words,int k) {
        //1、统计每个单词出现的次数 map
        HashMap<String,Integer> map = new HashMap<>();
        for (String s:words) {
              if(map.get(s) == null) {
                  map.put(s,1);
              }else {
                  int val = map.get(s);
                  map.put(s,val+1);
              }
        }
        //2、建立一个大小为K的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                //是为了避免大根堆的元素放不满时，有两个value值相等的，就需要通过关键字的大小来确定存放位置
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        //3、遍历Map
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            //判断大根堆里是否放满k对数据
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                //判断堆顶元素和当前数据的大小关系
                Map.Entry<String,Integer> top = minHeap.peek();
                //当堆顶元素的value值(出现频率)和entry中相同时，需要判断其k值的大小，判断哪个留在堆中
                if(top.getValue().compareTo(entry.getValue()) == 0) {
                    //如果top的关键字(单词)大于entry的就出堆，让key值小的进堆
                    if(top.getKey().compareTo(entry.getKey()) > 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    //大根堆的堆顶元素出现频率，比当前比较的小，那就将出现频率较高的入堆
                    if(top.getValue().compareTo(entry.getValue()) < 0) {
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}
